import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class Main {
    //找是否是循环
    public int fun(int n){
        int sum = 0;
        int k = 0;
        while(n>0){
            k = n%10;
            sum+=k*k;
            n/=10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int fast = fun(n);
        int slow = n;
        while(fast!=slow){
            fast = fun(fun(fast));
            slow = fun(slow);
        }
        if(fast == 1){
            return true;
        }else{
            return false;
        }
    }
    //移动0
    public void moveZeroes(int[] nums) {
        int dest = -1;
        for(int cur = 0;cur<nums.length;cur++){
            if(nums[cur]!=0){
                dest++;
                int tmp = nums[dest];
                nums[dest] = nums[cur];
                nums[cur] = tmp;
            }
        }
    }
    //复写零
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        int l = arr.length;
        //找到开始复写的位置
        while(dest<=(l-1)){
            if(arr[cur]==0){
                dest+=2;
            }else{
                dest++;
            }
            if(dest>=(l-1)) break;
            cur++;
        }
        //处理边界超出问题
        if(dest==l){
            arr[dest-1] = 0;
            cur--;
            dest-=2;
        }
        //从左到右开始复写
        while(cur>=0){
            if(arr[cur]!=0){
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
    //找盛水最多的容器
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int ret = 0;
        int l = 0;
        int h = 0;
        while(left < right){
            l = right - left;
            h = Math.min(height[left],height[right]);
            ret = Math.max(l*h,ret);
            if(height[left]<=height[right]){
                left++;
            }else{
                right--;
            }
        }
        return ret;
    }
    //找一个数组中有多少对可以组成三角形
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int ret = 0;
        Arrays.sort(nums);
        for(int i = n-1;i>=2;i--){//固定最大数
            int l = 0 , r = i - 1;
            while(l<r){
                if(nums[l]+nums[r]>nums[i]){
                    ret+=(r-l);
                    r--;
                }else{
                    l++;
                }
            }
        }
        return ret;
    }
    //查找数组中哪两个数和等于目标值
    public int[] twoSum(int[] price, int target) {
        int n = price.length;
        int l = 0, r = n-1;
        while(l<r){
            if(price[l]+price[r]>target){
                r--;
            }else if(price[l]+price[r]<target){
                l++;
            }else{
                return new int[]{price[l],price[r]};
            }
        }
        return new int[]{0};
    }
    //找数组中哪三个数之和等于0
    public List<List<Integer>> threeSum(int[] sums){
        List<List<Integer>> ret = new ArrayList<>();
        int n = sums.length;
        //給数组排序
        Arrays.sort(sums);
        //
        for(int i = 0;i<n-2;){
            int L = i+1;
            int R = n-1;
            while(L<R){
                if(sums[L]+sums[R]<-sums[i]){
                    L++;
                }else if(sums[L]+sums[R]>-sums[i]){
                    R--;
                }else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(sums[i],sums[L],sums[R])));
                    L++;
                    R--;
                    //去重
                    while(L<R&&sums[L]==sums[L+1]) L++;
                    while(L<R&&sums[R]==sums[R-1]) R--;
                }
            }
            i++;
            while(i<n-2&&sums[i]==sums[i-1]) i++;
        }
        return ret;
    }
    //四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new  ArrayList<>();
        Arrays.sort(nums);//排序
        int n = nums.length;
        for(int i = 0;i<n-3;){//固定a
            for(int j = i+1;j<n-2;){//固定b
                int L = j+1,R = n-1;
                long aim =(long)target - nums[i]-nums[j];
                while(L<R){
                    long sum= nums[L]+nums[R];
                    if(aim<sum){
                        R--;
                    }else if(aim>sum){
                        L++;
                    }else{
                        list.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        L++;
                        R--;
                        while(L<R&&nums[L]==nums[L-1]) L++;
                        while(L<R&&nums[R]==nums[R+1]) R--;
                    }
                }
                j++;
                while(j<n-2&&nums[j]==nums[j-1]) j++;
            }
            i++;
            while(i<n-3&&nums[i]==nums[i-1]) i++;
        }
        return list;
    }
}
